package org.example.myleet.p675;

import java.util.*;

public class Solution {

    private static final int GROUND = 1;
    private static final int OBSTACLE = 0;

    private static final int[][] DIRECTIONS = new int[][]{{-1, 0}, {0, 1}, {1, 0}, {0, -1}};

    public int cutOffTree(List<List<Integer>> forest) {
        int m = forest.size(), n = forest.get(0).size(), treeCount = 0;
        //统计所有树的数量
        for (int r = 0; r < m; ++r) {
            for (int c = 0; c < n; ++c) {
                if (forest.get(r).get(c) > GROUND) {
                    ++treeCount;
                }
            }
        }
        //用BFS的方式，将树按照由低到高维护在小根堆中
        PriorityQueue<int[]> treeSeqQueue = new PriorityQueue<>(new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return forest.get(o1[0]).get(o1[1]) - forest.get(o2[0]).get(o2[1]);
            }
        });
        boolean[][] visited = new boolean[m][n];
        Deque<int[]> deque = new LinkedList<>();
        deque.offer(new int[]{0, 0});
        visited[0][0] = true;
        if (forest.get(0).get(0) > GROUND) {
            treeSeqQueue.offer(new int[]{0, 0});
        }
        while (!deque.isEmpty()) {
            int size = deque.size();
            for (int i = 0; i < size; ++i) {
                int[] p = deque.poll();
                for (int j = 0; j < 4; ++j) {
                    int nr = p[0] + DIRECTIONS[j][0];
                    int nc = p[1] + DIRECTIONS[j][1];
                    if (0 <= nr && nr < m && 0 <= nc && nc < n) {
                        int val = forest.get(nr).get(nc);
                        if (val > OBSTACLE && !visited[nr][nc]) {
                            deque.offer(new int[]{nr, nc});
                            visited[nr][nc] = true;
                            if (val > GROUND) {
                                treeSeqQueue.offer(new int[]{nr, nc});
                            }
                        }
                    }
                }
            }
        }
        if (treeCount > treeSeqQueue.size()) {
            //说明有些树被障碍阻隔开，够不到
            return -1;
        }
        //经过上面的检验，可以确认所有树都可以走得到，下面开始模拟操作，每次用BFS确定移动的最少步数
        int optCount = 0;
        //保存上一个停留的点，例如砍树后停留的点
        int[] lastStop = new int[]{0, 0};
        //保存相同高度待砍的树，操作过程中需要优先砍完这些相同高度树再砍更高的树
        Map<String, int[]> cutCandidates = new HashMap<>();
        while (!treeSeqQueue.isEmpty()) {
            //从小根堆中取出需要砍的树的高度，以及所有高度相同的树
            int[] cutCandidate = treeSeqQueue.poll();
            cutCandidates.put(cutCandidate[0] + "_" + cutCandidate[1], cutCandidate);
            int tall = forest.get(cutCandidate[0]).get(cutCandidate[1]);
            while (!treeSeqQueue.isEmpty()) {
                int[] nextCutCandidate = treeSeqQueue.peek();
                if (tall == forest.get(nextCutCandidate[0]).get(nextCutCandidate[1])) {
                    cutCandidate = treeSeqQueue.poll();
                    cutCandidates.put(cutCandidate[0] + "_" + cutCandidate[1], cutCandidate);
                } else {
                    break;
                }
            }
            while (!cutCandidates.isEmpty()) {
                //下面不断循环用BFS找出所有相同高度树并砍掉，用BFS到达树可以知道每次操作的最小步数
                if (cutCandidates.containsKey(lastStop[0] + "_" + lastStop[1])) {
                    //停留位置上的树直接砍掉
                    forest.get(lastStop[0]).set(lastStop[1], GROUND);
                    cutCandidates.remove(lastStop[0] + "_" + lastStop[1]);
                    continue;
                }
                int step = 1;
                visited = new boolean[m][n];
                deque = new LinkedList<>();
                deque.offer(lastStop);
                visited[lastStop[0]][lastStop[1]] = true;
                BFS:
                while (!deque.isEmpty()) {
                    int size = deque.size();
                    for (int i = 0; i < size; ++i) {
                        int[] p = deque.poll();
                        for (int j = 0; j < 4; ++j) {
                            int nr = p[0] + DIRECTIONS[j][0];
                            int nc = p[1] + DIRECTIONS[j][1];
                            if (0 <= nr && nr < m && 0 <= nc && nc < n) {
                                int val = forest.get(nr).get(nc);
                                if (val > OBSTACLE && !visited[nr][nc]) {
                                    deque.offer(new int[]{nr, nc});
                                    visited[nr][nc] = true;
                                    if (val > GROUND && val == tall) {
                                        //找到一颗离lastStop最近的树，砍掉，更新lastStop
                                        forest.get(nr).set(nc, GROUND);
                                        cutCandidates.remove(nr + "_" + nc);
                                        lastStop = new int[]{nr, nc};
                                        break BFS;
                                    }
                                }
                            }
                        }
                    }
                    ++step;
                }
                optCount += step;
            }
        }
        return optCount;
    }
}
